#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <string>
#include <sstream>
using namespace std;

class Solution
{
public:
	vector<string> restoreIpAddresses(string s) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		vector<string> results;

		size_t nums[4];
		restorePartAddress(s,0,0,nums,results);

		return results;
	}
private:
	//nPart indicates which part it is, it can be 0,1,2,3
	void restorePartAddress(const string& s, size_t preSum,int nPart,size_t nums[4],vector<string>& results)
	{

		if(nPart==4)
		{
			ostringstream oss;
			oss<<s.substr(0,nums[0]);
			size_t ps = nums[0];
			for(int i=1;i<nPart;i++)
			{
				oss<<"."<<s.substr(ps,nums[i]);
				ps+= nums[i];
			}
			results.push_back(oss.str());
		}

		
		size_t minLeftLen = 1*(3-nPart), maxLeftLen = 3*(3-nPart);


		for(size_t i=1;i<=3;i++)
		{
			if((preSum+i)>s.size())
				return;
			size_t curLeft = s.size()-preSum-i;

			if(((curLeft<minLeftLen) || (curLeft>maxLeftLen)))
				continue;


			if(i==2 && s[preSum] == '0')
				continue;
			if(i==3)
			{
				int num = (s[preSum]-'0')*100 + (s[preSum+1]-'0')*10 + (s[preSum+2]-'0');
				if(num>255 || s[preSum]=='0')
					continue;
			}
			nums[nPart] = i;
			restorePartAddress(s,preSum+i,nPart+1,nums,results);
		}
	}

};
#endif